935D - Fafa and Ancient Alphabet - CodeForces Solution

#include <bits/stdc++.h>
#define int long long
using namespace std;
int mod = 1e9 +7;
int modinv_m;
int val;
int binexp(int x, int y)
{
    if(y==0)
        return 1;
    if(y&1)
        return (binexp((x*x)%mod, y/2) * x)%mod;
    else
        return (binexp((x*x)%mod, y/2))%mod;
}
int calculate(vector<int> &a, vector<int> &b, int n, int m, int i)
{
    if(i==n)
        return 0;
    for(;i<n;i++)
    {
        // cout<<a[i]<<" "<<b[i]<<endl; 
        if(a[i] == b[i] && a[i]!=0)
            continue;
        if(a[i] == b[i])
            return ((calculate(a,b,n,m,i+1) + (val*modinv_m)%mod)*modinv_m)%mod;
        else if(a[i] == 0)
        {
            // cout<<"Test\n";
            return ((calculate(a,b,n,m,i+1)+(m-b[i]))*modinv_m)%mod;
        }
        else if(b[i] == 0)
            return ((calculate(a,b,n,m,i+1)+(a[i]-1))*modinv_m)%mod;
        else if(a[i]>b[i])
            return 1;
        else
            return 0;
    }
    return 0;
}
void solve()
{
    int n, m;
    cin>>n>>m;
    modinv_m = binexp(m,mod-2)%mod;
    val = (m*(m-1))/2;
    vector<int> a(n);
    vector<int> b(n);
    for(int i=0;i<n;i++)
        cin>>a[i];
    for(int i=0;i<n;i++)
        cin>>b[i];
    int p = (calculate(a,b,n,m,0))%mod;
    cout<<p<<endl;
}
int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int t=1;
    // cin>>t;
    for(int i=1;i<=t;i++)
    {
        // cout<<"Testcase: "<<i<<endl;
        solve();
    }
    return 0;
}